10493. Коты в и без шляп

Кот носит шляпу тогда и только тогда, когда в шляпе находится в точности n котов. Существует только один кот, который находится не в шляпе. Если m котов не имеют шляп, то сколько всего котов?

Вход. Каждая строка содержит два числа n и m (1 £ n £ 100000, 1 £ m £ 100000). Последний тест содержит n = m = 0 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести n и m. Далее в этой же строке вывести общее количество котов (если оно определяется однозначно). Если решения нет, то вывести “Impossible”. Если имеется бесконечное количество решений, то вывести “Multiple”.

Пример входа	Пример выхода
3 3 3 4 2 5 0 0	3 3 4 3 4 Impossible 2 5 9

РЕШЕНИЕ

математика

Подсказка

1. Изобразите конструкцию котов и шляп для первого теста (n = 3 и m = 3).

2. Изобразите конструкцию котов и шляп для третьего теста (n = 2 и m = 5).

3. Какой ответ будет если n = 1 и m = 1?

4. Какой ответ будет если n = 1 и m > 1?

5. Пусть k – число шляп. Сколько всего котов? Ответ дать в виде выражения, зависящего от n и k.

6. Если на кота одеть шляпу, то на сколько увеличится общее количество котов без шляп?

7. Количество котов без шляп равно m. Выразить это значение через n и k.

8. Если k – целое число (количество шляп), то каким будет необходимое и достаточное условие существования решения? И в каком случае ответ будет “Impossible”?

9. Выразить k через m и n.

10. Общее количество котов вычислено в пункте 5. Подставив в него выражение для k из пункта 9, получим общее количество котов, выраженное через m и n.

11. В каких случаях ответом задачи будет “Multiple”?

Анализ алгоритма

При n = 1 и m = 1 существует бесконечное количество решений. Коты могут иметь любое из ниже приведенных расположений:

Если n = 1, m > 1, то решений не существует.

Пусть k – число шляп. Поскольку в каждой из k шляп находится n котов, то всего число котов равно 1 + nk (плюс единственный кот, который не находится в шляпе). При надевании на кота одной шляпы число котов без шляп увеличивается на n – 1. Таким образом, если сначала был один кот без шляпы, и было добавлено k шляп, то количество котов без шляп равно 1 + (n – 1) * k = m. Поскольку число шляп k = (m – 1) / (n – 1) целое, то m – 1 должно делиться без остатка на n – 1 (в противном случае требуемой конструкции шляп и котов не существует). Таким образом, получаем общее число котов: 1 + nk = 1 + n * (m – 1) / (n – 1).

Пример

Рассмотрим расположение котов для третьего теста (n = 2, m = 5):

Всего 9 котов. В каждой шляпе находится 2 кота, 5 котов не имеют шляп.

Реализация алгоритма

Читаем входные данные пока n ¹ 0. Если n = 1, то при m > 1 выводим сообщение о невозможности такой структуры котов, при m = 1 число котов может быть произвольным.

while (scanf("%d %d",&n,&m),n)

{

printf("%d %d ",n,m);

if (n == 1)

if (m > 1) printf("Impossible\n"); else printf("Multiple\n");

Проверяем, делится ли m – 1 на n – 1. Если не делится – ответ "Impossible". Иначе вычисляем число котов по выше приведенной формуле и печатаем ответ.

else if ((m - 1) % (n - 1))

printf("Impossible\n");

else

{

res = 1 + (m - 1) / (n - 1) * n;

printf("%d\n",res);

}

}